package com.qf.arith;

/**
 *
 * 一棵二叉搜索树，
 *    默认：至多二个孩子
 *          小的孩子在左边 、大的孩子在右边
 *    先序遍历结果为：5  2  1  3  4  6  8  7  9
 *
 *
 *    求后序遍历结果。  1 4 3 2 7 9 8 6 5
 *      使用Java代码来实现
 * @author lixu
 */
public class TestTwoTree {

    /**
     * 树 的数据结构
     * @param <E>
     */
    static class Node<E>{
        E value;//树枝上的值
        Node<E> right;//右子树
        Node<E> left;//左子树
        public Node(E value) {
            this.value = value;
        }
    }

    /**
     *  HashMap：
     *    哈希表 + 链表 + 红黑树
     *
     *    链表长度n(规模） 间复杂度： O(n)
     *    树 的时间复杂度： O(log2n)
     *
     *    log2n=8  ==  3~4
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        //1:准备二叉搜索树
        Integer[] arr = {5,2,1,3,4,6,8,7,9};//先序遍历结果
        //2:创建树
        //2.1:树的根
        Node<Integer> tree = new Node<>(arr[0]);//根只有一个
        //2.2:树的子节点 （N多个）
        for (int i = 1; i < arr.length; i++) {
            //插入子节点到树上
            insertTree(tree,arr[i]);
        }
        //验证树是正确
        //System.out.println(tree.left.right.right.value);
        //打印先序遍历结果
        printResult(tree);
        //
        Integer v = 10;
        //上面这个V的值在树中是否存在 ？
        System.out.println("是否存在" + v + ":" + searchTree(tree,v));

    }

    /**
     * 算法
     *  查询节点是否存在
     * @param tree
     * @param v
     * @return
     */
    private static boolean searchTree(Node<Integer> tree, Integer v) {

        //判断根是否是
        if(tree.value == v){
            return true;
        }
        if(tree.value > v){
            //判断左子树
            if(tree.left != null){
                return searchTree(tree.left,v);
            }
        }else{
            //判断右子树
            if(tree.right != null){
                return searchTree(tree.right,v);
            }
        }
        //不存在
        return false;

    }

    /**
     * 打印先序遍历   将整颗树进行遍历    O(n)   树有N个节点   == 链表
     * @param tree
     */
    private static void printResult(Node<Integer> tree) {
        //先序遍历 : 根  左子树  右子树
        //后序遍历：
        //左子树
        if(tree.left != null) printResult(tree.left);
        //右子树
        if(tree.right != null) printResult(tree.right);
        //根
        System.out.print(tree.value + " ");
    }

    /**
     * 链表  ： 保存节点  O(log2n) 性能高 比链表高
     * 树： ：  查询节点   O(log2n) 性能高 比链表高
     *
     *   ES：索引
     *   Mysql：索引
     *
     *   索引：  是否使用的是树
     *
     *   哈希表：时间复杂度 O(1)  不能排序
     *
     *   select * from 表    order by 索引部分排序          100万
     *
     *   select * from 表    order by id desc  limit 6
     *
     *
     * 将子节点以二叉搜索树规则插入到树的上面    O(log2n) = 3   O(log3n)
     * @param tree
     */
    private static void insertTree(Node<Integer> tree,Integer value) {
        //tree:根
        if(value > tree.value){//1
            //保存在右子树上
            if(tree.right == null){//1
                //没有右子树
                tree.right = new Node(value);//1
            }else{
                //已有右子树
                insertTree(tree.right,value);//1
            }
        }else{
            //保存在左子树上
            if(tree.left == null){
                //没有左子树
                tree.left = new Node(value);
            }else{
                //已有左子树
                insertTree(tree.left,value);
            }
        }
    }


//    public static void main(String[] args) {
//        面试题：
//        已知一棵二叉树
//        先序遍历结果为：1 2 4 6 3 5 7 8
//        中序遍历结果为：2 6 4 1 7 5 8 3
            //1、画出图来
            //2、Java代码
//        求后序遍历结果。










    //}
}
